#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// 224. 基本计算器
// 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
class Solution {
public:
    int calculate(string s) {
        s += " ";   // 在字符串末尾加个空格，以便最后累计的数字放到tokens中
        vector<string> tokens;  // 后缀表达式
        string number;
        bool needsZero = true;  // 是否需要补0
        for(char ch : s) {
            if(ch >= '0' && ch <= '9') {
                number += ch;
                needsZero = false;
                continue;
            } else {
                if(!number.empty()) {   // 数字进入中缀表达式
                    tokens.push_back(number);
                    number = "";
                }
            }

            if(ch == ' ') continue; // 过滤掉空格
            if(ch == '(') {
                ops.push(ch);
                needsZero = true;
                continue;
            }
            if(ch == ')') {
                while(ops.top() != '(') {
                    tokens.push_back(string(1,ops.top()));  // 这里要push一个字符的字符串，不能是一个ASCII码，即to_string(ops.top())
                    ops.pop();
                }
                ops.pop();
                needsZero = false;
                continue;
            }
            if((ch == '+' || ch == '-') && needsZero) {
                tokens.push_back("0");  // 补0
            }
            int currRank = getRank(ch);
            while(!ops.empty() && getRank(ops.top()) >= currRank) {
                tokens.push_back(string(1,ops.top()));
                ops.pop();
            }
            ops.push(ch);
            needsZero = true;
        }

        while (!ops.empty()) {
            tokens.push_back(string(1,ops.top()));  // 这里要push一个字符的字符串，不能是一个ASCII码，即to_string(ops.top())
            ops.pop();
        }
//        for(string& token : tokens) cout << token << endl;
        return evalRPN(tokens);
    }

private:
    stack<char> ops;    // 操作符栈
    int getRank(char ch) {
        if(ch == '*' || ch == '/') return 2;
        if(ch == '+' || ch == '-') return 1;
        return 0;
    }
    // 计算逆波兰表达式
    stack<int> st;
    int calc(int x,int y,string& op) {
        if(op == "+") return x+y;
        if(op == "-") return x-y;
        if(op == "*") return x*y;
        if(op == "/") return x/y;
        return 0;
    }
    int evalRPN(vector<string>& tokens) {
        for(string& token : tokens) {
            if(token == "+" || token == "-" || token == "*" || token == "/") {
                int y = st.top();
                st.pop();
                int x = st.top();
                st.pop();
                int z = calc(x,y,token);
                st.push(z);
            } else {
                st.push(atoi(token.c_str()));   // 字符串转化为整数
            }
        }
        return st.top();
    }
};
int main() {
    std::cout << Solution().calculate("1 + 1") << std::endl;    // 2
    std::cout << Solution().calculate(" 2-1 + 2 ") << std::endl;    // 3
    std::cout << Solution().calculate("(1+(4+5+2)-3)+(6+8)") << std::endl;  // 23
    std::cout << Solution().calculate("1-(     -2)") << std::endl;  // 3
    return 0;
}
